package exercise.week01;

import java.util.HashSet;
import java.util.LinkedList;

/**
 * 7届-决赛-JavaB-3
 * 打靶
 * <p>
 * 小明参加X星球的打靶比赛。
 * 比赛使用电子感应计分系统。其中有一局，小明得了96分。
 * <p>
 * 这局小明共打了6发子弹，没有脱靶。
 * 但望远镜看过去，只有3个弹孔。
 * 显然，有些子弹准确地穿过了前边的弹孔。
 * <p>
 * 不同环数得分是这样设置的：
 * 1,2,3,5,10,20,25,50
 * <p>
 * 那么小明的6发子弹得分都是多少呢？有哪些可能情况呢？
 */
public class T3 {
    public static int sum = 0;

    public static void main(String[] args) {
        int[] score = {1, 2, 3, 5, 10, 20, 25, 50};
        LinkedList<Integer> list = new LinkedList<Integer>();
        HashSet<Integer> set = new HashSet<Integer>();
        dfs(score, set, 1, list);
    }

    public static void dfs(int[] score, HashSet<Integer> set, int level, LinkedList<Integer> result) {
        //截止条件
        if (level > 6) {
            if (set.size() == 3) {
                for (Integer i : result) {
                    sum += i;
                }
                if (sum == 96) {
                    for (Integer i : result) {
                        System.out.print(i + " ");
                    }
                }
            }
            System.out.println();
            return;
        }
        //候选结点
        for (int i = 0; i < score.length; i++) {
            result.push(score[i]);
            set.add(score[i]);
            dfs(score, set, level + 1, result);
            result.pop();
            set.remove(score[i]);
        }
    }
}
